package com.zhupf.binaryTree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhupf
 * @date 2023年12月07日 15:38
 * @Description
 *
 * 236. 二叉树的最近公共祖先
 */
public class LowestCommonAncestor {

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        this.process(root,p,q);
        return ans;
    }

    private TreeNode ans;

    public int process(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return 0;
        }
        int res = 0;
        if(root.val == p.val || root.val == q.val){
            res = 1;
        }
        int left = process(root.left,p,q);
        int right = process(root.right,p,q);
        res = res + left + right;
        if(left != 2 && right != 2 &&  res == 2){
            ans = root;
        }
        return res;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root.val == p.val || root.val == q.val){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        return root;
    }


}
